#include<iostream>
#include<vector>

//思想1：1.先去除vector中的nullptr；2.然后再遍历找出最小值；
//外排序；https://blog.csdn.net/FX677588/article/details/72471357

using namespace std;

struct ListNode { 
    int val; struct ListNode *next; 
    ListNode(int x) : val(x), next(NULL) { }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        ListNode *dummy=new ListNode(0);
        ListNode *head=dummy;
        ListNode *cur=nullptr;
        for(auto iter=lists.begin();iter!=lists.end();){
            if(*iter==nullptr){
                iter=lists.erase(iter);
            }else{
                ++iter;
            }
        }
        while(!lists.empty()){
            cur=*lists.begin();
            int index=0;
            for(int i=1;i<lists.size();++i){
                if(cur->val > lists[i]->val){
                    cur=lists[i];
                    index=i;
                }
            }
            lists[index]=lists[index]->next;
            if(lists[index] == nullptr){
                lists.erase(lists.begin()+index);
            }
            head->next=cur;
            head=head->next;
        }
        return dummy->next;
    }
};